第49章栈、队列与循环队列

栈、队列和循环队列是计算机科学中最基础且应用广泛的线性数据结构，它们通过特定的元素插入和删除规则，实现对数据的有序管理

49.1 栈(Stack)

49.1.1 定义与特性

栈是一种后进先出（Last In First Out，LIFO）原则的线性数据结构，即后插入的元素最先被删除。栈的操作仅在一端进行，这一端被称为栈顶，另一端则被称为栈底。形象比喻：栈类似于叠放的盘子，只能从最顶端放置或取走盘子，先放的盘子被压在底部，最后放的盘子最先被取走。

49.1.2 基本操作

栈的核心操作包括：

入栈(Push)：将元素添加到栈顶，栈的大小增加1。
出栈(Pop)：删除栈顶元素，栈的大小减少1（需先判断是否为空）。
取元素(Top/Peek)：返回栈顶元素的值，不改变栈的结构（需先判断是否为空）。
判空(IsEmpty)：判断栈是否为空，若为空返回true，否则返回false。
获取大小(Size)：返回栈中元素的个数。

49.1.3 实现方式

栈可通过数组或链表实现，数组实现更高效，链表实现更灵活。

数组实现

#include <iostream>
#include <cstring>
using namespace std;
const int MAX_SIZE=100;
class Stack {
private:
    int data[MAX_SIZE];//存储栈元素的数组
    int top;//栈顶指针(指向栈顶元素的下标,-1表示空栈)
public:
    //构造函数:初始化空栈
    Stack(){
        top= -1;
    }
    //入栈
    bool push (int val) {
        if (top >= MAX_SIZE - 1){
            return false;//栈满，入栈失败
        }
        data[++top]= val;//栈顶指针先加1，再存入元素
        return true;
    }
    //出栈
    bool pop(){
        if (isEmpty()){
            return false;//栈空，出栈失败
        }
        top--;//栈顶指针减1(逻辑上移除元素)
        return true;
    }
    //取栈顶元素
    int topVal(){
        if (isEmpty()){
            throw "Stack is empty";
        }
        return data[top];
    }
    //判空
    bool isEmpty(){
        return top == -1;
    }
    //获取大小
    int size(){
        return top + 1;
    }
};

链表实现

#include <iostream>
using namespace std;
//链表节点结构
struct Node{
    int val;
    Node* next;
    Node (int v):val(v),next (nullptr){}
};
class Stack {
private:
    Node* top;//栈顶指针(指向栈顶节点)
    int size;
public:
    //构造函数:初始化空栈
    Stack(){
        top = nullptr;
        size=0;
    }
    //析构函数:释放所有节点
    ~Stack(){
        while (top!= nullptr){
            Node* temp=top;
            top= top->next;
            delete temp;
        }
    }
    //入栈
    void push (int val){
        Node* newNode = new Node (val);
        newNode->next= top;//新节点指向原栈顶
        top=newNode;//更新栈顶指针
        size++;
    }
    //出栈
    bool pop(){
        if (isEmpty()){
            return false;
        }
        Node* temp= top;
        top=top->next;//栈顶指针后移
        delete temp;
        size--;
        return true;
    }
    //取栈顶元素
    int topVal(){
        if (isEmpty()){
            throw "Stack is empty";
        }
        return top->val;
    }
    //判空
    bool isEmpty(){
        return top == nullptr;
    }
    //获取大小
    int getSize(){
        return size;
    }
};

49.1.4 应用场景

函数调用：程序执行时，函数调用的上下文（返回地址、局部变量等）通过栈存储，函数返回时从栈顶弹出。
表达式求值：如后缀表达式（逆波兰表达式）的计算，利用栈存储操作数，遇到运算符时弹出操作数计算。
括号匹配：检查代码中括号是否成对出现，遇到左括号入栈，遇到右括号时与栈顶左括号匹配并出栈。
撤销操作：文本编辑器中的"撤销"功能，通过记录操作历史，撤销时弹出最近的操作。

49.2 队列(Queue)

49.2.1 定义与特性

队列是一种先进先出（First In First Out，FIFO）原则的线性数据结构，元素的入队在一端（队尾）进行，元素的删除在另一端（队头）进行。形象比喻：队列类似于排队购票，先排队的人先购票离开，后排队的人依次等待，符合"先来后到"的规则。

49.2.2 基本操作

队列的核心操作包括:

入队(Enqueue)：将元素添加到队尾，队列大小增加1。
出队(Dequeue)：删除队头元素，队列大小减少1（需先判断队列是否为空）。
取队头元素(Front)：返回队头元素的值，不改变队列结构（需先判断队列是否为空）。
判空(IsEmpty)：判断队列是否为空，若为空返回true，否则返回false。
获取大小(Size)：返回队列中元素的个数。

49.2.3 实现方式

队列可通过数组或链表实现，链表实现更适合动态大小场景，数组实现需注意队头和队尾的指针管理。

链表实现

#include<iostream>
using namespace std;
//链表节点结构
struct Node{
    int val;
    Node* next;
    Node (int v): val(v), next (nullptr) {}
};
class Queue{
private:
    Node* front;//队头指针(指向第一个元素)
    Node* rear;//队尾指针(指向最后一个元素)
    int size;
public:
    //构造函数:初始化空队列
    Queue(){
        front = rear = nullptr;
        size=0;
    }
    //析构函数:释放所有节点
    ~Queue(){
        while (front!= nullptr){
            Node* temp= front;
            front = front->next;
            delete temp;
        }
    }
    //入队
    void enqueue(int val){
        Node* newNode = new Node (val);
        if (isEmpty()){
            front= rear=newNode;//空队列时，队头和队尾指向新节点
        } else{
            rear->next=newNode;//新节点链接到队尾
            rear=newNode;//更新队尾指针
        }
        size++;
    }
    //出队
    bool dequeue(){
        if(isEmpty()){
            return false;
        }
        Node* temp = front;
        front = front->next;//队头指针后移
        if (front == nullptr) {
            rear=nullptr;//队列变空时，队尾指针也置空
        }
        delete temp;
        size--;
        return true;
    }
    //取队头元素
    int getFront(){
        if (isEmpty()){
            throw"Queue is empty";
        }
        return front->val;
    }
    //判空
    bool isEmpty(){
        return front == nullptr;
    }
    //获取大小
    int getSize(){
        return size;
    }
};

数组实现(简单版，存在空间浪费问题)

#include <iostream>
using namespace std;
const int MAX_SIZE = 100;
class Queue{
private:
    int data[MAX_SIZE];
    int front;//队头指针(指向队头元素)
    int rear;//队尾指针(指向队尾元素的下一个位置)
    int size;
public:
    Queue(){
        front=0;
        rear=0;
        size=0;
    }
    //入队
    bool enqueue (int val) {
        if (size == MAX_SIZE){
            return false;//队列满
        }
        data[rear]= val;
        rear=(rear +1) % MAX_SIZE;//循环移动(为后续循环队列铺垫)
        size++;
        return true;
    }
    //出队
    bool dequeue(){
        if (isEmpty()){
            return false;
        }
        front =(front +1) % MAX_SIZE;
        size--;
        return true;
    }
    //取队头元素
    int getFront(){
        if (isEmpty()){
            throw "Queue is empty";
        }
        return data[front];
    }
    bool isEmpty(){
        return size==0;
    }
    int getSize(){
        return size;
    }
};

49.2.4 应用场景

任务调度：操作系统中的进程调度、打印机任务队列，按请求顺序处理任务。
广度优先搜索(BFS)：遍历图或树时，使用队列存储待访问节点，确保按层次顺序访问。
缓冲处理：如键盘输入缓冲、网络数据接收缓冲，按到达顺序处理数据。
消息队列：分布式系统中，不同组件间通过消息队列传递消息，保证消息的有序处理。

49.3 循环队列(Circular Queue)

49.3.1 定义与特性

循环队列是对普通数组队列的优化，通过将数组的首尾相连（逻辑上形成环形），解决普通数组队列因队头移动导致的空间浪费问题。循环队列的队头和队尾指针在达到数组末尾时，会绕回数组的起始位置，从而高效利用存储空间。核心解决的问题：普通数组队列中，即使队列元素个数小于数组容量，若队尾已到达数组末尾，也无法继续入队（假溢出）；循环队列通过环形逻辑，允许队尾绕回数组头部，充分利用空间。

49.3.2 基本操作

循环队列的操作与普通队列一致，核心区别在于队头和队尾指针的移动方式（采用模运算实现循环）。

49.3.3 实现方式

循环队列通常通过数组实现，关键是如何判断队列满和队列空：判空条件：front==rear且元素个数为0。判满条件：通常通过预留一个空位置实现，即(rear+1)%MAX_SIZE == front，此时队列中实际可存储MAX_SIZE-1个元素。

#include <iostream>
using namespace std;
const int MAX_SIZE = 100;
class CircularQueue {
private:
    int data[MAX_SIZE];
    int front;//队头指针(指向队头元素)
    int rear;//队尾指针(指向队尾元素的下一个位置)
public:
    //构造函数:初始化空队列
    CircularQueue(){
        front=0;
        rear=0;
    }
    //入队
    bool enqueue (int val){
        if (isFull()){
            return false;//队列满
        }
        data[rear] = val;
        rear=(rear + 1) % MAX_SIZE;//队尾指针循环后移
        return true;
    }
    //出队
    bool dequeue(){
        if (isEmpty()){
            return false;//队列空
        }
        front =(front+1) % MAX_SIZE; //队头指针循环后移
        return true;
    }
    //取队头元素
    int getFront(){
        if (isEmpty()){
            throw "CircularQueue is empty";
        }
        return data[front];
    }
    //判空
    bool isEmpty(){
        return front == rear;
    }
    //判满(预留一个空位置)
    bool isFull(){
        return (rear + 1) % MAX_SIZE == front;
    }
    //获取大小
    int getSize(){
        return (rear - front + MAX_SIZE) % MAX_SIZE;
    }
};

49.3.4 优势与应用场景

优势

空间利用率高：避免普通数组队列的"假溢出"问题，充分利用数组空间。
操作高效：入队和出队操作的时间复杂度均为 $$O(1)$$ ，与普通队列一致。

应用场景

固定大小的缓冲池：如嵌入式系统中的数据缓冲区，内存资源有限，需高效利用空间。
生产者-消费者模型：当生产者和消费者速度不匹配时，循环队列可作为中间缓冲，平衡两者的处理速度。
实时数据处理：如传感器数据采集，固定容量的循环队列可存储最新的N条数据，旧数据自动被新数据覆盖。

49.4 三种数据结构的对比

数据结构	核心原则	操作端	典型实现	时间复杂度 (基本操作)	主要应用
栈	后进先出 (LIFO)	仅栈顶	数组、链表	$O(1)$	函数调用、括号匹配、表达式求值
队列	先进先出 (FIFO)	队头(出)、队尾(入)	链表、数组	$O(1)$	任务调度、 BFS、缓冲处理
循环队列	先进先出 (FIFO)	队头(出)、队尾(入)	数组	$O(1)$	固定大小缓冲、生产者-消费者模型

49.5 注意事项

边界条件处理：栈和队列的出队、取元素操作前必须判空；入队操作前判满，避免越界错误。
内存管理：链表实现的栈和队列需在析构函数中释放所有节点，防止内存泄漏。
循环队列的容量：采用预留空位置判满的循环队列，实际可存储的元素个数为MAX_SIZE-1，需根据需求调整数组大小。
选择合适的实现方式：
- 若元素数量固定且已知，优先使用数组实现（效率高）。
- 若元素数量动态变化，优先使用链表实现（灵活性好）。
- 若需高效利用数组空间且大小固定，选择循环队列。

49.1 栈(Stack)​

49.1.1 定义与特性​

49.1.2 基本操作​

49.1.3 实现方式​

数组实现​

链表实现​

49.1.4 应用场景​

49.2 队列(Queue)​

49.2.1 定义与特性​

49.2.2 基本操作​

49.2.3 实现方式​

链表实现​

数组实现(简单版，存在空间浪费问题)​

49.2.4 应用场景​

49.3 循环队列(Circular Queue)​

49.3.1 定义与特性​

49.3.2 基本操作​

49.3.3 实现方式​

49.3.4 优势与应用场景​

优势​

应用场景​

49.4 三种数据结构的对比​

49.5 注意事项​

49.1 栈(Stack)

49.1.1 定义与特性

49.1.2 基本操作

49.1.3 实现方式

数组实现

链表实现

49.1.4 应用场景

49.2 队列(Queue)

49.2.1 定义与特性

49.2.2 基本操作

49.2.3 实现方式

链表实现

数组实现(简单版，存在空间浪费问题)

49.2.4 应用场景

49.3 循环队列(Circular Queue)

49.3.1 定义与特性

49.3.2 基本操作

49.3.3 实现方式

49.3.4 优势与应用场景

优势

应用场景

49.4 三种数据结构的对比

49.5 注意事项